package com.cat.dataStructure;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/
 * @create 2025/8/23 15:06
 * @since JDK17
 */

public class Solution45 {
    int n, m, ans;
    int[][] arr;
    public void init(int[][]mat) {
        for (int a = 1, b = 0; b < n; a++, b++) {
            for (int c = 1, d = 0; d < m; c++, d++) {
                arr[a][c] = mat[b][d];
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
            }
        }
    }
    int sum(int a, int b, int c, int d) {
        return arr[c][d] - arr[c][b - 1] - arr[a - 1][d] + arr[a - 1][b - 1];
    }

    public int maxSideLength(int[][] mat, int threshold) {
        n = mat.length;
        m = mat[0].length;
        arr = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int k = ans + 1; k + i <= n && k + j <= m; k++) {
                    if (sum(i, j, i + k, j + k) <= threshold) {
                        ans = k;
                    }
                }
            }
        }

        return ans;
    }
}
